package leetcode_600;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *@author 周杨
 *MinimumIndexSumOfTwoLists_599 找两个字典里相同元素最小索引和
 *describe:遍历即可 AC 40%
 *2018年9月18日 上午10:48:36
 */
public class MinimumIndexSumOfTwoLists_599 {
	public String[] findRestaurant(String[] list1, String[] list2) {
        Map<String,Integer> map1=new HashMap<String,Integer>();
        for(int i=0;i<list1.length;++i) {
        	map1.put(list1[i], i);
        }
        Map<Integer,List<String>> map2=new HashMap<Integer,List<String>>();
        int min=Integer.MAX_VALUE;
        for(int i=0;i<list2.length;++i) {
        	if(map1.containsKey(list2[i])) {//必须两个列表都包含
        		int index=i+map1.get(list2[i]);
        		min=Math.min(min, index);
        		List<String> list=map2.get(index);
        		if(list==null) {
        			list=new ArrayList<String>();
        			list.add(list2[i]);
        			map2.put(index, list);
        		}
        		else {
        			list.add(list2[i]);
        		}
        	}
        }
        List<String> minList=map2.get(min);
        String []res=new String[minList.size()];
        for(int i=0;i<minList.size();++i) {
        	res[i]=minList.get(i);
        }
        return res;
       
	}
}
